﻿using System;

namespace _98._验证二叉搜索树
{
    /// <summary>
    /// https://leetcode.cn/problems/validate-binary-search-tree/
    /// </summary>
    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
        {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public class Solution
    {
        public bool IsValidBST(TreeNode root)
        {
            return IsValidBST(root, long.MinValue, long.MaxValue);
        }

        public bool IsValidBST(TreeNode node, long lower, long upper)
        {
            if (node == null)
            {
                return true;
            }
            if (node.val <= lower || node.val >= upper)
            {
                return false;
            }

            return IsValidBST(node.left, lower, node.val) && IsValidBST(node.right, node.val, upper);
        }
        long pre = long.MinValue;
        /// <summary>
        /// 中序遍历，因为
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public bool IsValidBST2(TreeNode root)
        {
            if (root == null) return true;

            bool a = IsValidBST2(root.left);

            if (root.val <= pre)
            {
                return false;
            }

            pre = root.val;
            Console.WriteLine(root.val);

            bool b = IsValidBST2(root.right);

            return a && b;
        }

    }
    class Program
    {
        static void Main(string[] args)
        {
            TreeNode nodes = new TreeNode(2, new TreeNode(1), new TreeNode(3));
            Console.WriteLine(new Solution().IsValidBST(nodes));
            Console.WriteLine(new Solution().IsValidBST2(nodes));

            Console.WriteLine();

            nodes = new TreeNode(5, new TreeNode(1), new TreeNode(4, new TreeNode(3), new TreeNode(6)));
            Console.WriteLine(new Solution().IsValidBST(nodes));
            Console.WriteLine(new Solution().IsValidBST2(nodes));

            Console.WriteLine();

            nodes = new TreeNode(1, null, new TreeNode(1));
            Console.WriteLine(new Solution().IsValidBST(nodes));
            Console.WriteLine(new Solution().IsValidBST2(nodes));

            Console.WriteLine();

            nodes = new TreeNode(0, new TreeNode(-1));
            Console.WriteLine(new Solution().IsValidBST(nodes));
            Console.WriteLine(new Solution().IsValidBST2(nodes));
        }
    }
}
